home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / c_news / 10 / database / bplus.c next >
C/C++ Source or Header  |  1988-07-31  |  25KB  |  942 lines
  1. /********************************************************************/
  2. /*                                                                  */
  3. /*             BPLUS file indexing program - Version 1.1            */
  4. /*                                                                  */
  5. /*                      A "shareware program"                       */
  6. /*                                                                  */
  7. /*                                                                  */
  8. /*                      Copyright (C) 1987 by                       */
  9. /*                                                                  */
  10. /*                      Hunter and Associates                       */
  11. /*                      7050 NW Zinfandel Lane                      */
  12. /*                      Corvallis, Oregon  97330                    */
  13. /*                      (503) 745 - 7186                            */
  14. /*                                                                  */
  15. /********************************************************************/
  16.  
  17.  
  18. #include <stdio.h>
  19. #include <fcntl.h>
  20. #include <io.h>
  21. /* #include <sys\types.h>         **  delete this line for Turbo C  */
  22. #include <sys\stat.h>
  23. #include <string.h>
  24. #include <bplus.h>
  25.  
  26.  
  27. /*  macros, constants, data types  */
  28.  
  29. #define  NULLREC      (-1L)
  30. #define  FREE_BLOCK   (-2)
  31.  
  32. #define  ENT_ADR(pb,off)  ((ENTRY*)((char*)((pb)->entries) + off))
  33. #define  ENT_SIZE(pe)     strlen((pe)->key) + 1 + 2 * sizeof(RECPOS)
  34. #define  BUFDIRTY(j)      (mci->cache[j].dirty)
  35. #define  BUFHANDLE(j)     (mci->cache[j].handle)
  36. #define  BUFBLOCK(j)      (mci->cache[j].mb)
  37. #define  BUFCOUNT(j)      (mci->cache[j].count)
  38. #define  CB(j)            (pci->pos[j].cblock)
  39. #define  CO(j)            (pci->pos[j].coffset)
  40.  
  41.  
  42. /*  declare some global variables  */
  43.  
  44. IX_DESC      *pci;
  45. IX_BUFFER    bt_buffer;
  46. IX_BUFFER    *mci = &bt_buffer;
  47. BLOCK        *block_ptr;
  48. BLOCK        *spare_block;
  49. int          cache_ptr = 0;
  50. int          cache_init = 0;
  51. int          split_size = IXB_SPACE;
  52. int          comb_size  = (IXB_SPACE/2);
  53.  
  54. void pascal error(int, long);
  55. void pascal read_if(long, char *, int);
  56. void pascal write_if(int, long, char *, int);
  57. int  pascal creat_if(char *);
  58. int  pascal open_if(char *);
  59. void pascal close_if(int);
  60. void pascal update_block(void);
  61. void pascal init_cache(void);
  62. int  pascal find_cache(RECPOS);
  63. int  pascal new_cache(void);
  64. void pascal load_cache(RECPOS);
  65. void pascal get_cache(RECPOS);
  66. void pascal retrieve_block(int, RECPOS);
  67. int  pascal prev_entry(int);
  68. int  pascal next_entry(int);
  69. int  pascal copy_entry(ENTRY *, ENTRY *);
  70. int  pascal scan_blk(int);
  71. int  pascal last_entry(void);
  72. int  pascal write_free( RECPOS, BLOCK *);
  73. RECPOS pascal get_free(void);
  74. int  pascal find_block(ENTRY *, int *);
  75. void pascal movedown(BLOCK *, int, int);
  76. void pascal moveup(BLOCK *, int, int);
  77. void pascal ins_block(BLOCK *, ENTRY *, int);
  78. void pascal del_block(BLOCK *, int);
  79. int  pascal split(int, ENTRY *, ENTRY *);
  80. void pascal ins_level(int, ENTRY *);
  81. int  pascal insert_ix(ENTRY *, IX_DESC *);
  82. int  pascal find_ix(ENTRY *, IX_DESC *, int);
  83. int  pascal combineblk(RECPOS, int);
  84. void pascal replace_entry(ENTRY *);
  85. void print_blk(BLOCK *);
  86.  
  87.  
  88. /*  file I/O for B-PLUS module  */
  89.  
  90. void pascal error(j, l)
  91.   int j;
  92.   long l;
  93.   {
  94.     static char *msg[3] = {"ERROR - CANNOT OPEN/CLOSE FILE",
  95.                            "ERROR WHILE READING FILE",
  96.                            "ERROR WHILE WRITING FILE"};
  97.     printf("\n  %s - Record Number %ld\n", msg[j], l);
  98.     exit(1);
  99.   } /* error */
  100.  
  101.  
  102. void pascal read_if(start, buf, nwrt)
  103.   long start;
  104.   char *buf;
  105.   int nwrt;
  106.   {
  107.     long err;
  108.     err = start - lseek(pci->ixfile, start, SEEK_SET);
  109.     if (err == 0) err = nwrt - read(pci->ixfile, buf, nwrt);
  110.     if (err != 0) error(1, start);
  111.   } /* read_if */
  112.  
  113.  
  114. void pascal write_if(handle, start, buf, nwrt)
  115.   int handle;
  116.   long start;
  117.   char *buf;
  118.   int nwrt;
  119.   {
  120.     long err;
  121.     err = start - lseek(handle, start, SEEK_SET);
  122.     if (err == 0) err = nwrt - write(handle, buf, nwrt);
  123.     if (err != 0) error(2, start);
  124.   } /* write_if */
  125.  
  126.  
  127. int pascal creat_if(fn)
  128.   char *fn;
  129.   {
  130.     int   ret;
  131.     ret = open(fn,O_RDWR|O_CREAT|O_TRUNC|O_BINARY,S_IWRITE);
  132.     if (ret  < 0) error(0,0L);
  133.     return (ret);
  134.   } /* creat_if */
  135.  
  136.  
  137. int pascal open_if(fn)
  138.   char *fn;
  139.   {
  140.     int  ret;
  141.     ret = open(fn,O_RDWR|O_BINARY);
  142.     if (ret < 1) error(0,0L);
  143.     return (ret);
  144.   } /* open_if */
  145.  
  146.  
  147. void pascal close_if(handle)
  148.   int handle;
  149.   {
  150.     if(close(handle) < 0)  error(2,0L);
  151.   } /*  close_if */
  152.  
  153.  
  154. int cdecl open_index(name, pix, dup)
  155.   char *name;
  156.   IX_DESC *pix;
  157.   int dup;
  158.   {
  159.     pci = pix;
  160.     pci->ixfile = open_if(name);
  161.     pci->duplicate = dup;
  162.     read_if(0L,(char *)&(pix->root), (sizeof(BLOCK) + sizeof(IX_DISK)));
  163.     if (!cache_init)
  164.       {
  165.         init_cache();
  166.         cache_init = 1;
  167.       }
  168.     first_key(pix);
  169.     return ( IX_OK );
  170.   } /* open_index */
  171.  
  172.  
  173. int cdecl close_index(pix)
  174.   IX_DESC *pix;
  175.   {
  176.     int i;
  177.     write_if(pix->ixfile, 0L,(char *)&(pix->root),
  178.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  179.     for (i = 0; i < NUM_BUFS; i++)
  180.       if (BUFHANDLE(i) == pix->ixfile)
  181.         {
  182.           if (BUFDIRTY(i))
  183.             {
  184.               write_if(BUFHANDLE(i),
  185.                        BUFBLOCK(i).brec,
  186.                        (char *) &BUFBLOCK(i),
  187.                        sizeof(BLOCK));
  188.               BUFDIRTY(i) = 0;
  189.             }
  190.           BUFBLOCK(i).brec = NULLREC;
  191.       }
  192.     close_if(pix->ixfile);
  193.     return( IX_OK );
  194.   } /* close_index */
  195.  
  196.  
  197. int cdecl make_index(name, pix, dup)
  198.   char *name;
  199.   IX_DESC *pix;
  200.   int dup;
  201.   {
  202.     pci = pix;
  203.     pci->ixfile = creat_if(name);
  204.     pci->duplicate = dup;
  205.     pci->dx.nl = 1;
  206.     pci->dx.ff = NULLREC;
  207.     pci->level = 0;
  208.     CO(0) = -1;
  209.     CB(0) = 0L;
  210.     pci->root.brec = 0L;
  211.     pci->root.bend = 0;
  212.     pci->root.p0 = NULLREC;
  213.     write_if(pci->ixfile, 0L,(char *)&(pix->root),
  214.                (sizeof(BLOCK) + sizeof(IX_DISK)));
  215.     if (!cache_init)
  216.       {
  217.         init_cache();
  218.         cache_init = 1;
  219.       }
  220.     first_key(pix);
  221.     return ( IX_OK );
  222.   } /* make_index */
  223.  
  224.  
  225. /*  cache I/O for BPLUS  */
  226.  
  227. void pascal update_block()
  228.   {
  229.     if (block_ptr != &(pci->root))
  230.        BUFDIRTY(cache_ptr) = 1;
  231.   } /* update_block */
  232.  
  233.  
  234. void pascal init_cache()
  235.   {
  236.     register int  j;
  237.     for (j = 0; j < NUM_BUFS; j++)
  238.       {  BUFDIRTY(j) = 0;
  239.          BUFCOUNT(j) = 0;
  240.          BUFBLOCK(j).brec = NULLREC;
  241.       }
  242.   } /* init_cache */
  243.  
  244.  
  245. int pascal find_cache(r)
  246.   RECPOS r;
  247.   {
  248.     register int  j;
  249.     for (j = 0; j < NUM_BUFS; j++)
  250.       {
  251.         if((BUFBLOCK(j).brec == r) && (BUFHANDLE(j) == pci->ixfile))
  252.          {  cache_ptr = j;
  253.             return (1);
  254.       }  }
  255.     return (-1);
  256.   } /* find_cache */
  257.  
  258.  
  259. int pascal new_cache()
  260.   {
  261.     register int  i;
  262.     i = (cache_ptr + 1) % NUM_BUFS;
  263.     if (BUFDIRTY(i)) write_if(BUFHANDLE(i),
  264.                               BUFBLOCK(i).brec,
  265.                               (char *) &BUFBLOCK(i),
  266.                               sizeof(BLOCK));
  267.     BUFHANDLE(i) = pci->ixfile;
  268.     BUFDIRTY(i) = 0;
  269.     return (i);
  270.   } /* new_cache */
  271.  
  272.  
  273. void pascal load_cache(r)
  274.   RECPOS r;
  275.   {
  276.     cache_ptr = new_cache();
  277.     read_if(r, (char *)&BUFBLOCK(cache_ptr), sizeof(BLOCK));
  278.   } /* load_cache */
  279.  
  280.  
  281. void pascal get_cache(r)
  282.   RECPOS r;
  283.   {
  284.     if (find_cache(r) < 0)
  285.        load_cache(r);
  286.     block_ptr = &BUFBLOCK(cache_ptr);
  287.   } /* get_cache */
  288.  
  289.  
  290. void pascal retrieve_block(j, r)
  291.   int j;
  292.   RECPOS r;
  293.   {
  294.     if (j == 0)
  295.        block_ptr = &(pci->root);
  296.     else  get_cache(r);
  297.     CB(j) = block_ptr->brec;
  298.   } /* retrieve_block */
  299.  
  300.  
  301. /*  low level functions of BPLUS  */
  302.  
  303. int pascal prev_entry(off)
  304.   int off;
  305.   {
  306.      if (off <= 0)
  307.        {
  308.          off = -1;
  309.          CO(pci->level) = off;
  310.        }
  311.      else
  312.        off = scan_blk(off);
  313.      return(off);
  314.   } /* prev_entry */
  315.  
  316.  
  317. int pascal next_entry(off)
  318.   int off;
  319.   {
  320.      if (off == -1)
  321.        off = 0;
  322.      else
  323.        {
  324.          if (off < block_ptr->bend)
  325.             off += ENT_SIZE(ENT_ADR(block_ptr,off));
  326.        }
  327.      CO(pci->level) = off;
  328.      return (off);
  329.   } /* next_entry */
  330.  
  331.  
  332. int pascal copy_entry(to, from)
  333.   ENTRY *to;
  334.   ENTRY *from;
  335.   {
  336.     int me;
  337.     me = ENT_SIZE(from);
  338.     memmove(to, from, me);
  339.   } /* copy_entry */
  340.  
  341.  
  342. int pascal scan_blk(n)
  343.   int n;
  344.   {
  345.      register int off, last;
  346.      off = 0;
  347.      last = -1;
  348.      while (off < n )
  349.        {  last = off;
  350.           off += ENT_SIZE(ENT_ADR(block_ptr,off));
  351.        }
  352.      CO(pci->level) = last;
  353.      return (last);
  354.   } /* scan_blk */
  355.  
  356.  
  357. int pascal last_entry()
  358.   {
  359.      return( scan_blk(block_ptr->bend) );
  360.   } /* last_entry */
  361.  
  362.  
  363. /*  maintain list of free index blocks  */
  364.  
  365. int pascal write_free(r, pb)
  366.   RECPOS r;
  367.   BLOCK *pb;
  368.   {
  369.     pb->p0 = FREE_BLOCK;
  370.     pb->brec = pci->dx.ff;
  371.     write_if(pci->ixfile, r, (char *) pb, sizeof(BLOCK));
  372.     pci->dx.ff = r;
  373.   } /* write_free */
  374.  
  375.  
  376. RECPOS pascal get_free()
  377.   {
  378.     RECPOS  r, rt;
  379.  
  380.     r = pci->dx.ff;
  381.     if ( r != NULLREC )
  382.       {  read_if(r, (char *)&rt, sizeof( RECPOS ));
  383.          pci->dx.ff = rt;
  384.       }
  385.     else
  386.       r = filelength (pci->ixfile);
  387.     return (r);
  388.   } /* get_free */
  389.  
  390.  
  391. /*  general BPLUS block level functions  */
  392.  
  393. int pascal find_block(pe, poff)
  394.   ENTRY *pe;
  395.   int *poff;
  396.   {
  397.     register int pos, nextpos, ret;
  398.     pos = -1;
  399.     nextpos = 0;
  400.     ret = 1;
  401.     while ( nextpos < block_ptr->bend)
  402.       {
  403.         ret = strcmp((char *)(pe->key),
  404.                      (char *)(ENT_ADR(block_ptr, nextpos)->key));
  405.         if (ret <= 0)
  406.           {
  407.              if (ret == 0) pos = nextpos;
  408.              break;
  409.           }
  410.         pos = nextpos;
  411.         nextpos = next_entry(pos);
  412.       }
  413.     CO(pci->level) = pos;
  414.     *poff = pos;
  415.     return (ret);
  416.   } /* find_block */
  417.  
  418.  
  419. void pascal movedown(pb, off, n)
  420.   BLOCK *pb;
  421.   int off;
  422.   int n;
  423.   {
  424.     memmove(ENT_ADR(pb, off),
  425.            ENT_ADR(pb, off + n),
  426.            pb -> bend - (off + n));
  427.   } /* movedown */
  428.  
  429.  
  430. void pascal moveup(pb, off, n)
  431.   BLOCK *pb;
  432.   int off;
  433.   int n;
  434.   {
  435.     memmove(ENT_ADR(pb, off + n),
  436.             ENT_ADR(pb, off),
  437.             pb->bend - off);
  438.   } /* moveup */
  439.  
  440.  
  441. void pascal ins_block(pb, pe, off)
  442.   BLOCK *pb;
  443.   ENTRY *pe;
  444.   int off;
  445.   {
  446.     int size;
  447.     size = ENT_SIZE(pe);
  448.     moveup(pb,off,size);
  449.     copy_entry(ENT_ADR(pb,off),pe);
  450.     pb->bend += size;
  451.   } /* ins_block */
  452.  
  453.  
  454. void pascal del_block(pb, off)
  455.   BLOCK *pb;
  456.   int off;
  457.   {
  458.     int ne;
  459.     ne = ENT_SIZE(ENT_ADR(pb, off));
  460.     movedown(pb, off, ne);
  461.     pb->bend -= ne;
  462.   } /* del_block */
  463.  
  464.  
  465. /*  position at start/end of index  */
  466.  
  467. int cdecl first_key(pix)
  468.   IX_DESC *pix;
  469.   {
  470.     pci = pix;
  471.     block_ptr = &(pci->root);
  472.     CB(0) = 0L;
  473.     CO(0) = -1;
  474.     pci->level = 0;
  475.     while(block_ptr->p0 != NULLREC)
  476.       {
  477.         retrieve_block(++(pci->level), block_ptr->p0);
  478.         CO(pci->level) = -1;
  479.       }
  480.     return ( IX_OK );
  481.   } /* first_key */
  482.  
  483.  
  484. int cdecl last_key(pix)
  485.   IX_DESC *pix;
  486.   {
  487.     long  ads;
  488.     pci = pix;
  489.     block_ptr = &(pci->root);
  490.     CB(0) = 0L;
  491.     pci->level = 0;
  492.     if(last_entry() >= 0)
  493.       {
  494.         while ((ads = ENT_ADR(block_ptr,last_entry())->idxptr) != NULLREC)
  495.              retrieve_block(++(pci->level), ads);
  496.       }
  497.     CO(pci->level) = block_ptr->bend;
  498.     return ( IX_OK );
  499.   } /* last_key */
  500.  
  501.  
  502. /*  get next, previous entries  */
  503.  
  504. int cdecl next_key(pe, pix)
  505.   ENTRY *pe;
  506.   IX_DESC *pix;
  507.   {
  508.     RECPOS  address;
  509.     pci = pix;
  510.     retrieve_block(pci->level, CB(pci->level));
  511.     if(CO(pci->level) == -1) address = block_ptr->p0;
  512.     else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  513.     while (address != NULLREC)
  514.       {
  515.          retrieve_block(++(pci->level), address);
  516.          CO(pci->level) = -1;
  517.          address = block_ptr->p0;
  518.       }
  519.     next_entry(CO(pci->level));
  520.     if (CO(pci->level) == block_ptr->bend)
  521.       {
  522.         do
  523.           { if(pci->level == 0)
  524.               {
  525.                 last_key(pci);
  526.                 return (EOIX);
  527.               }
  528.             --(pci->level);
  529.             retrieve_block(pci->level, CB(pci->level));
  530.             next_entry(CO(pci->level));
  531.           } while (CO(pci->level) == block_ptr->bend);
  532.       }
  533.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  534.     return ( IX_OK );
  535.   } /* next_key */
  536.  
  537.  
  538. int cdecl prev_key(pe, pix)
  539.   ENTRY *pe;
  540.   IX_DESC *pix;
  541.   {
  542.     RECPOS  address;
  543.     pci = pix;
  544.     retrieve_block(pci->level, CB(pci->level));
  545.     prev_entry(CO(pci->level));
  546.     if (CO(pci->level) == -1)
  547.       address = block_ptr->p0;
  548.     else
  549.       address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  550.     if (address != NULLREC)
  551.       { do
  552.           {
  553.             retrieve_block(++(pci->level), address);
  554.             address = ENT_ADR(block_ptr, last_entry())->idxptr;
  555.           } while (address != NULLREC);
  556.       }
  557.     if (CO(pci->level) == -1)
  558.       { do
  559.           {
  560.             if(pci->level == 0)
  561.               {
  562.                 first_key(pci);
  563.                 return (EOIX);
  564.               }
  565.             --(pci->level);
  566.           } while (CO(pci->level) == -1);
  567.         retrieve_block(pci->level, CB(pci->level));
  568.       }
  569.     copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  570.     return ( IX_OK );
  571.   } /* prev_key */
  572.  
  573.  
  574. /*  insert new entries into tree  */
  575.  
  576. int pascal split(l, pe, e)
  577.   int l;
  578.   ENTRY *pe;
  579.   ENTRY *e;
  580.   {
  581.     int  half, ins_pos, size;
  582.     ins_pos = CO(pci->level);
  583.     half = scan_blk(block_ptr->bend / 2 + sizeof(RECPOS));
  584.     if (half == ins_pos)
  585.       *e = *pe;
  586.     else
  587.       {
  588.          copy_entry(e, ENT_ADR(block_ptr, half));
  589.          size = ENT_SIZE(e);
  590.          movedown(block_ptr, half, size);
  591.          block_ptr->bend -= size;
  592.       }
  593.     spare_block = &BUFBLOCK(new_cache());
  594.     memmove(spare_block->entries,
  595.            ENT_ADR(block_ptr,half),
  596.            block_ptr->bend - half);
  597.     spare_block->brec = get_free();
  598.     spare_block->bend = block_ptr->bend - half;
  599.     spare_block->p0 = e->idxptr;
  600.     block_ptr->bend = half;
  601.     e->idxptr = spare_block->brec;
  602.     if (ins_pos < half)
  603.       ins_block(block_ptr,pe,ins_pos);
  604.     else if (ins_pos > half)
  605.       {
  606.          ins_pos -= ENT_SIZE(e);
  607.          ins_block(spare_block,pe,ins_pos - half);
  608.          CB(l) = e->idxptr;
  609.          CO(l) = CO(l) - half;
  610.       }
  611.     write_if(pci->ixfile, spare_block->brec,
  612.              (char *) spare_block, sizeof(BLOCK));
  613.   } /* split */
  614.  
  615.  
  616. void pascal ins_level(l, e)
  617.   int l;
  618.   ENTRY *e;
  619.   {
  620.     int  i;
  621.     if ( l < 0)
  622.       {  for (i = 1; i < MAX_LEVELS; i++)
  623.            {  CO(MAX_LEVELS - i) = CO(MAX_LEVELS - i - 1);
  624.               CB(MAX_LEVELS - i) = CB(MAX_LEVELS - i - 1);
  625.            }
  626.          memmove(spare_block, &(pci->root), sizeof(BLOCK));
  627.          spare_block->brec = get_free();
  628.          write_if(pci->ixfile, spare_block->brec,
  629.                   (char *) spare_block, sizeof(BLOCK));
  630.          pci->root.p0 = spare_block->brec;
  631.          copy_entry((ENTRY *) (pci->root.entries), e);
  632.          pci->root.bend = ENT_SIZE(e);
  633.          CO(0) = 0;
  634.          pci->level = 0;
  635.          (pci->dx.nl)++;
  636.       }
  637.     else ins_block(block_ptr,e,CO(l));
  638.   } /* ins_level */
  639.  
  640.  
  641. int pascal insert_ix(pe, pix)
  642.   ENTRY *pe;
  643.   IX_DESC *pix;
  644.   {
  645.     ENTRY    e, ee;
  646.     int h;
  647.     h = 0;
  648.     pci = pix;
  649.     ee = *pe;
  650.     do
  651.       {
  652.          if(CO(pci->level) >= 0)
  653.            CO(pci->level) +=
  654.                   ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level)));
  655.          else
  656.            CO(pci->level) = 0;
  657.          update_block();
  658.          if( (block_ptr->bend + ENT_SIZE(&ee)) <= split_size)
  659.            {
  660.              ins_level(pci->level, &ee);
  661.              break;
  662.            }
  663.          else
  664.            {
  665.              h = 1;
  666.              split(pci->level,&ee, &e);
  667.               ee = e;
  668.               pci->level--;
  669.               if (pci->level < 0)
  670.                 {
  671.                   ins_level(pci->level, &e);
  672.                   break;
  673.                 }
  674.               retrieve_block(pci->level, CB(pci->level));
  675.            }
  676.       }
  677.     while (1);
  678.     if (h) find_ix(pe, pix, 0);
  679.     return ( IX_OK );
  680.   } /* insert_ix */
  681.  
  682.  
  683. /*  BPLUS find and add key functions  */
  684.  
  685. int pascal find_ix(pe, pix, find)
  686.   ENTRY *pe;
  687.   IX_DESC *pix;
  688.   int find;
  689.   {
  690.     int      level, off, ret;
  691.     RECPOS   ads;
  692.     ENTRY    found;
  693.     pci = pix;
  694.     ads = 0L;
  695.     level = ret = 0;
  696.     while (ads != NULLREC)
  697.       {  pci->level = level;
  698.          retrieve_block(level, ads);
  699.          if (find_block(pe, &off) == 0) ret = 1;
  700.          if (ret && find) break;
  701.          if (off == -1)
  702.            ads = block_ptr->p0;
  703.          else
  704.            ads = ENT_ADR(block_ptr, off)->idxptr;
  705.          CO(level++) = off;
  706.        }
  707.      return ( ret );
  708.    } /* find_ix */
  709.  
  710.  
  711. int cdecl find_key(pe, pix)
  712.   ENTRY *pe;
  713.   IX_DESC *pix;
  714.   {
  715.     int ret;
  716.     ret = find_ix(pe, pix, 1);
  717.     if ( ret ) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  718.     return ( ret );
  719.   } /* find_key */
  720.  
  721.  
  722. int cdecl add_key(pe, pix)
  723.   ENTRY *pe;
  724.   IX_DESC *pix;
  725.   {
  726.     int ret;
  727.     ret = find_ix(pe, pix, 0);
  728.     if ( ret && (pci->duplicate == 0)) return ( IX_FAIL );
  729.     pe->idxptr = NULLREC;
  730.     return (insert_ix(pe, pix));
  731.   } /* add_key */
  732.  
  733.  
  734. int cdecl locate_key(pe, pix)
  735.   ENTRY *pe;
  736.   IX_DESC *pix;
  737.   {
  738.     int ret;
  739.     ENTRY e;
  740.     ret = find_ix(pe, pix, 1);
  741.     if (ret) copy_entry(pe, ENT_ADR(block_ptr, CO(pci->level)));
  742.     else if (next_key(pe,pix) == EOIX) ret = EOIX;
  743.     return ( ret );
  744.   } /* locate_key */
  745.  
  746.  
  747. int cdecl find_exact(pe, pix)
  748.   ENTRY *pe;
  749.   IX_DESC * pix;
  750.   {
  751.     int  ret;
  752.     ENTRY e;
  753.     copy_entry(&e, pe);
  754.     ret = find_key(&e, pix);
  755.     if ( ret && pci->duplicate)
  756.       {
  757.         do
  758.           {
  759.             ret = (e.recptr == pe->recptr);
  760.             if( !ret )  ret = next_key(&e, pci);
  761.             if (ret) ret = (strcmp(e.key, pe->key) == 0);
  762.             if ( !ret ) return ( 0 );
  763.           } while ( !ret );
  764.       }
  765.     copy_entry(pe, &e);
  766.     return ( ret );
  767.   } /* find_exact */
  768.  
  769.  
  770. /* BPLUS delete key functions */
  771.  
  772. int cdecl delete_key(pe, pix)
  773.   ENTRY *pe;
  774.   IX_DESC *pix;
  775.   {
  776.      ENTRY   e;
  777.      RECPOS  ads;
  778.      int     h, leveli, levelf;
  779.      if (!find_exact(pe, pix))  return( IX_FAIL );
  780.      h = 1;
  781.      if ((ads = pe->idxptr) != NULLREC)
  782.        {
  783.           leveli = pci->level;
  784.           do
  785.             {
  786.                retrieve_block(++(pci->level), ads);
  787.                CO(pci->level) = -1;
  788.             }
  789.           while ((ads = block_ptr->p0) != NULLREC);
  790.           CO(pci->level) = 0;
  791.           copy_entry(&e, ENT_ADR(block_ptr, CO(pci->level)));
  792.           levelf = pci->level;
  793.           pci->level = leveli;
  794.           replace_entry(&e);
  795.           pci->level = levelf;
  796.        }
  797.      while ( h )
  798.        {
  799.           retrieve_block(pci->level, CB(pci->level));
  800.           del_block(block_ptr, CO(pci->level));
  801.           update_block();
  802.           if ( (pci->level == 0) && (block_ptr->bend == 0))
  803.           /* tree was reduced in height */
  804.             {
  805.               if (pci->root.p0 != NULLREC)
  806.                 {
  807.                   retrieve_block(++pci->level, pci->root.p0);
  808.                   memmove(&(pci->root), block_ptr, sizeof(BLOCK));
  809.                   (pci->dx.nl)--;
  810.                   write_free(block_ptr->brec, block_ptr);
  811.                   BUFDIRTY(cache_ptr) = 0;
  812.                   BUFHANDLE(cache_ptr) = 0;
  813.                 }
  814.               break;
  815.             }
  816.           h = (block_ptr->bend < comb_size) && (pci->level > 0);
  817.           if ( h )
  818.               h = combineblk(CB(pci->level), block_ptr->bend);
  819.        }
  820.     find_ix(pe,pix,0);
  821.     return( IX_OK );
  822.   } /* delete_key */
  823.  
  824.  
  825. int pascal combineblk(ads, size)
  826.   RECPOS ads;
  827.   int size;
  828.   {
  829.     ENTRY  e;
  830.     RECPOS address;
  831.     int    esize, off, ret, saveoff, ibuff;
  832.     ret = 0;
  833.     saveoff = CO(--(pci->level));
  834.     retrieve_block(pci->level, CB(pci->level));
  835.     if ((off = next_entry( saveoff )) < block_ptr->bend)
  836.       /* combine with page on right */
  837.       {
  838.         if ( (ENT_SIZE(ENT_ADR(block_ptr, off)) + size) < split_size)
  839.           {
  840.             copy_entry(&e, ENT_ADR(block_ptr, off));
  841.             address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  842.             retrieve_block(++pci->level, address);
  843.             ibuff = cache_ptr;
  844.             spare_block = block_ptr;
  845.             retrieve_block(pci->level, ads);
  846.             esize = ENT_SIZE(&e);
  847.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  848.                  && (spare_block->bend <= block_ptr->bend + esize))
  849.                return( ret );
  850.             e.idxptr = spare_block->p0;
  851.             ins_block(block_ptr, &e, block_ptr->bend);
  852.             update_block();
  853.             if ((block_ptr->bend + spare_block->bend) < split_size)
  854.             /* combine the blocks */
  855.               {
  856.                 memmove(ENT_ADR(block_ptr, block_ptr->bend),
  857.                        ENT_ADR(spare_block, 0),
  858.                        spare_block->bend);
  859.                 block_ptr->bend += spare_block->bend;
  860.                 write_free(spare_block->brec, spare_block);
  861.                 BUFDIRTY(ibuff) = 0;
  862.                 BUFHANDLE(ibuff) = 0;
  863.                 --pci->level;
  864.                 ret = 1;
  865.               }
  866.             else
  867.             /* move an entry up to replace the one moved */
  868.               {
  869.                 copy_entry(&e, ENT_ADR(spare_block, 0));
  870.                 esize = ENT_SIZE(&e);
  871.                 movedown(spare_block, 0, esize);
  872.                 spare_block->bend -= esize;
  873.                 spare_block->p0 = e.idxptr;
  874.                 BUFDIRTY(ibuff) = 1;
  875.                 --(pci->level);
  876.                 replace_entry(&e);
  877.               }
  878.           }
  879.       }
  880.     else
  881.       /* move from page on left */
  882.       {
  883.         if ( (ENT_SIZE(ENT_ADR(block_ptr, CO(pci->level))) + size)
  884.                  < split_size)
  885.           {
  886.             copy_entry(&e, ENT_ADR(block_ptr, saveoff));
  887.             off = prev_entry(saveoff);
  888.             if (CO(pci->level) == -1) address = block_ptr->p0;
  889.             else address = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  890.             retrieve_block(++pci->level, address);
  891.             off = last_entry();
  892.             ibuff = cache_ptr;
  893.             spare_block = block_ptr;
  894.             retrieve_block(pci->level, ads);
  895.             esize = ENT_SIZE(&e);
  896.             if(((block_ptr->bend + spare_block->bend + esize) >= split_size)
  897.                  && (spare_block->bend <= block_ptr->bend + esize))
  898.                return( ret );
  899.             BUFDIRTY(ibuff) = 1;
  900.             CO(pci->level) = 0;
  901.             e.idxptr = block_ptr->p0;
  902.             ins_block(block_ptr, &e, 0);
  903.             if ((block_ptr->bend + spare_block->bend) < split_size)
  904.             /* combine the blocks */
  905.               {
  906.                 memmove(ENT_ADR(spare_block, spare_block->bend),
  907.                        ENT_ADR(block_ptr, 0),
  908.                        block_ptr->bend);
  909.                 spare_block->bend += block_ptr->bend;
  910.                 write_free(block_ptr->brec, block_ptr);
  911.                 BUFDIRTY(cache_ptr) = 0;
  912.                 BUFHANDLE(cache_ptr) = 0;
  913.                 CO(--(pci->level)) = saveoff;
  914.                 ret = 1;
  915.               }
  916.             else
  917.             /* move an entry up to replace the one moved */
  918.               {
  919.                  block_ptr->p0 = ENT_ADR(spare_block,off)->idxptr;
  920.                  copy_entry(&e, ENT_ADR(spare_block, off));
  921.                  spare_block->bend = off;
  922.                  update_block();
  923.                  CO(--(pci->level)) = saveoff;
  924.                  replace_entry(&e);
  925.               }
  926.           }
  927.       }
  928.     return ( ret );
  929.   } /* combineblk */
  930.  
  931.  
  932. void pascal replace_entry(pe)
  933.   ENTRY *pe;
  934.   {
  935.     retrieve_block(pci->level, CB(pci->level));
  936.     pe->idxptr = ENT_ADR(block_ptr, CO(pci->level))->idxptr;
  937.     del_block(block_ptr, CO(pci->level));
  938.     prev_entry(CO(pci->level));
  939.     insert_ix(pe, pci);
  940.   } /* replace_entry */
  941.  
  942.